/*
 * DuList.c
 *
 *  Created on: 2011-5-2
 *      Author: william nie
 */

#include"DuList.h"

Status InitDuList(DuList **duListP) {

	printf("��ʼ��˫��ѭ�����?\n");
	(*duListP) = (DuList *) malloc(sizeof(DuList));

	(*duListP)->head = (DLElemType *) malloc(sizeof(DLElemType));
	(*duListP)->head->prior = (*duListP)->head->next = (*duListP)->head;
	(*duListP)->head ->data = 0;

	(*duListP) -> length = 0;
	(*duListP) -> listsize = ((*duListP) -> length + 1) * sizeof(DLElemType);

	printf("��ʼ��˫��ѭ��������ϡ�\n\n");

	return OK;

}

Status DestoryDuList(DuList **duListP) {
	DLElemType *listHead = (*duListP)->head;
	DLElemType *elemToDestory = (*duListP)->head->next;

	while (elemToDestory != listHead) {
		free(elemToDestory->prior);
		elemToDestory = elemToDestory->next;
	}

	free(*duListP);
	*duListP = NULL;

	return OK;
}

Status ClearDuList(DuList *duList) {
	DLElemType *listHead = duList->head;
	DLElemType *elem = listHead->next, *toClear;

	while (elem != listHead) {

		toClear = elem;
		free(toClear);

		elem = elem->next;
	}

	listHead->next = listHead->prior = listHead;

	duList->length = 0;
	duList->listsize = (duList->length + 1) * sizeof(DuList);

	return OK;
}

BOOL DuListEmpty(DuList *duList) {
	if (duList->length == 0) {
		return TRUE;
	} else {
		return FALSE;
	}
}

int DuListLength(DuList *duList) {
	return duList->length;
}

DLElemType* GetDuElem(DuList *duList, int loc) {

	if (loc < 0 || loc > duList->length) {
		fprintf(stderr, "Your loc is out of range!\nExit!");
		fflush(stdin);
		getchar();
		exit(ERROR);
	}

	DLElemType *elemToReturn = duList->head->next;
	int count = 1;

	for (; elemToReturn != duList->head && count < loc; count++) {
		elemToReturn = elemToReturn->next;
	}

	if (elemToReturn == duList->head) {
		fprintf(stderr, "Your elem is not found in this list!\nexit!");
		fflush(stdin);
		getchar();
		exit(ERROR);
	}

	return elemToReturn;
}

int LocateDuElem(DuList *duList, int elemToCompare, Compare rule) {

	DLElemType *listHead = duList->head;
	DLElemType *elem = listHead->next;
	int locate = 1;

	while (elem != listHead && !rule(elem->data, elemToCompare)) {
		elem = elem->next;
		locate++;
	}

	return locate;
}

DLElemType* PriorDuElem(DuList *duList, int elem) {

	DLElemType *elemToReturn = duList->head->next;

	while (elemToReturn != duList->head && elemToReturn->data != elem) {
		elemToReturn = elemToReturn->next;
	}

	if (elemToReturn == duList->head->next) {
		return duList->head->prior;
	}

	if (elemToReturn == duList->head) {
		fprintf(stderr, "No elem found in list!\nexit!");
		fflush(stdin);
		getchar();
		exit(ERROR);
	}

	return elemToReturn->prior;
}

DLElemType* NextDuElem(DuList *duList, int elem) {
	DLElemType *elemToReturn = duList->head->next;

	while (elemToReturn != duList->head && elemToReturn->data != elem) {
		elemToReturn = elemToReturn->next;
	}

	if (elemToReturn == duList->head->prior) {
		return duList->head->next;
	}

	if (elemToReturn == duList->head) {
		fprintf(stderr, "No elem found in list!\nexit!");
		fflush(stdin);
		getchar();
		exit(ERROR);
	}

	return elemToReturn->next;
}

Status DuListInsert(DuList *duList, int loc, int elem) {

	if (loc < 0 || loc > duList->length) {
		fprintf(stderr, "Your loc is out of range!\nExit!");
		fflush(stdin);
		getchar();
		exit(ERROR);
	}

	DLElemType *elemInLoc = GetDuElem(duList, loc);
	DLElemType *elemBeforeLoc = elemInLoc->prior;
	DLElemType *elemToInsert = (DLElemType *) malloc(sizeof(DLElemType));
	elemToInsert->data = elem;

	elemToInsert->prior = elemBeforeLoc;
	elemBeforeLoc->next = elemToInsert;

	elemToInsert->next = elemInLoc;
	elemInLoc->prior = elemToInsert;

	duList->length += 1;
	duList->listsize += sizeof(DuList);

	return OK;
}

Status DuListDelete(DuList *duList, int loc) {

	if (loc < 0 || loc > duList->length) {
		fprintf(stderr, "Your loc is out of range!\nExit!");
		fflush(stdin);
		getchar();
		exit(ERROR);
	}

	DLElemType *elemToDelete = GetDuElem(duList, loc);
	DLElemType *elemBeforeLoc = elemToDelete->prior;
	DLElemType *elemAfterLoc = elemToDelete->next;

	elemBeforeLoc->next = elemAfterLoc;
	elemAfterLoc->prior = elemBeforeLoc;

	free(elemToDelete);

	duList->length -= 1;
	duList->listsize -= sizeof(DuList);

	return OK;
}

BOOL DuListTraverse(DuList *duList, Visit visit) {
	DLElemType *listHead = duList->head;
	DLElemType *elemToTraverse = listHead->next;

	while (elemToTraverse != listHead) {
		if (!visit(elemToTraverse)) {
			return FALSE;
		}
	}
	return TRUE;
}

Status FillDuList(DuList *duList) {
	printf("Ϊ˫��ѭ������������ݡ�\n");

	DLElemType *listHead = duList->head;
	DLElemType *nextElem = listHead;
	int listLength = 0;
	int count = 0;
	printf("������?��\n");
	scanf("%d", &listLength);
	duList->length = listLength;

	duList->listsize = (listLength + 1) * sizeof(DuList);

	fflush(stdin);
	printf("�������Ԫ�أ�\n");

	for (; count < listLength; count++) {
		nextElem->next = (DLElemType *) malloc(sizeof(DLElemType));
		scanf("%d", &nextElem->next->data);
		nextElem->next->prior = nextElem;
		nextElem = nextElem->next;
	}

	nextElem->next = listHead;
	listHead->prior = nextElem;

	printf("Ϊ˫��ѭ���������������ϡ�\n\n");

	return OK;
}

Status PrintDuList(DuList *duList) {
	DLElemType *listHead = duList->head;
	DLElemType *elem = listHead->next;

	printf("��˫��ѭ������Ԫ�أ�\n");
	while (elem != listHead) {
		printf("%d ", elem->data);
		elem = elem->next;
	}

	printf("\n");
	printf("��˫��ѭ�����?�ȣ�\n");
	printf("%d\n", duList->length);
	printf("��˫��ѭ��������ռ�ڴ��С��\n");
	printf("%d\n\n", duList->listsize);

	return OK;
}

Status ReverseDuList(DuList *duList) {
	DLElemType *listHead = duList->head;
	DLElemType *elemReverse = duList->head->prior;
	DLElemType *elemTemp;

	while (elemReverse != listHead) {
		elemTemp = elemReverse->prior;
		elemReverse->prior = elemReverse->next;
		elemReverse->next = elemTemp;

		elemReverse = elemReverse->next;
	}

	elemTemp = listHead->prior;
	listHead->prior = listHead->next;
	listHead->next = elemTemp;

	return OK;
}

Status PrintDuListElem(DuList *duList) {
	DLElemType *listHead = duList->head;
	DLElemType *elem = listHead->next;

	while (elem != listHead) {
		printf("%d ", elem->data);
		elem = elem->next;
	}

	return OK;
}

BOOL DuDefaultCompare(int elem1, int elem2) {
	if (elem1 == elem2) {
		return TRUE;
	} else {
		return FALSE;
	}
}

BOOL DuDefaultVisit(DLElemType *elem) {
	printf("%d ", elem->data);
	return TRUE;
}
